//#include<iostream>
//using namespace std;
//int n, k;
//int t[10001]{ 0 };
//int l[10001]{ 0 };
//int max_rest[10001]{ 0 };
//int is_first[10001]{ 0 };
//int is_last[10001]{ 0 };
//int is_visited[10001]{ 0 };
//
//int existWork(int j, int i) {
//	for (int a = 1; a <= k; a++)
//		if (t[a] >= t[j] + l[j] && t[a] < t[i])
//			return a;
//	return 0;
//}
//int setFirst() {
//	int flag = 1;
//	int min_first_endtime = 100000;
//	for (int i = 1; i <= k; i++) {
//		flag = 1;
//		for (int j = 1; j <= k; j++)
//			if (t[j] < t[i]) {
//				flag = 0;
//				break;
//			}
//		if (flag) {
//			is_first[i] = 1;
//			min_first_endtime = min(min_first_endtime, t[i] + l[i] - 1);
//			is_visited[i] = 1;
//			max_rest[i] = t[i] - 1;
//		}
//	}
//	return min_first_endtime;
//}
//void setLast() {
//	int flag = 1;
//	for (int i = 1; i <= k; i++) {
//		flag = 1;
//		for (int j = 1; j <= k; j++)
//			if (t[j] >= t[i] + l[i]) {
//				flag = 0;
//				break;
//			}
//		if (flag)
//			is_last[i] = 1;
//	}
//}
//int isNotHappen(int i, int min_first_endtime) {
//	for (int j = 1; j <= k; j++)
//		if (is_first[j] && t[i] > t[j] && t[i] <= min_first_endtime)
//			return 1;
//	return 0;
//}
//int maxRest(int i, int min_first_endtime) {
//	if (is_first[i] && is_last[i])
//		return n - l[i];
//	if (is_visited[i])
//		return max_rest[i];
//	if (isNotHappen(i, min_first_endtime))
//		return -100000;
//	for (int j = 1; j <= k; j++)
//		if (t[j] + l[j] <= t[i] && !existWork(j, i))
//			max_rest[i] = max(max_rest[i], maxRest(j, min_first_endtime) + t[i] - (t[j] + l[j]));
//	if(is_last[i])
//		max_rest[i] += n - (t[i] + l[i] - 1);
//	is_visited[i] = 1;
//	return max_rest[i];
//}
//int main() {
//	cin >> n >> k;
//	for (int i = 1; i <= k; i++)
//		cin >> t[i] >> l[i];
//	int m = 0;
//	int min_first_endtime = setFirst();
//	setLast();
//	for (int i = 1; i <= k; i++){
//	
//		m = max(m, maxRest(i, min_first_endtime));
////		cout << "max_rest[" << i << "]:" << max_rest[i] << endl;
//	}
//	cout << m << endl;
//	return 0;
//}
////
//////#include<iostream>
//////using namespace std;
//////int existWork(int* t, int* l, int k, int j, int i) {
//////	for (int a = 1; a <= k; a++)
//////		if (t[a] >= t[j] + l[j] && t[a] < t[i])
//////			return a;
//////	return 0;
//////}
//////int isFirst(int* t, int* l, int k, int i) {
//////	for (int j = 1; j <= k; j++)
//////		if (t[j] < t[i])
//////			return 0;
//////	return 1;
//////}
//////int isLast(int* t, int* l, int k, int i) {
//////	for (int j = 1; j <= k; j++)
//////		if (t[j] >= t[i] + l[i])
//////			return 0;
//////	return 1;
//////}
//////int main() {
//////	int n, k;
//////	cin >> n >> k;
//////	int* t = (int*)calloc(k + 1, sizeof(int));
//////	int* l = (int*)calloc(k + 1, sizeof(int));
//////	for (int i = 1; i <= k; i++)
//////		cin >> t[i] >> l[i];
//////	int i, j;
//////	int m = 0;
//////	int* max_rest = (int*)calloc(k + 1, sizeof(int));
//////	int* is_include_first = (int*)calloc(k + 1, sizeof(int));
//////	for (int a = 1; a <= k; a++)
//////		if (isFirst(t, l, k, a)) {
//////			max_rest[a] += t[a] - 1;
//////			is_include_first[a] = 1;
//////		}
//////	for (i = 1; i <= k; i++) {
//////		for (j = 1; j <= k; j++)
//////			if (t[j] + l[j] <= t[i] && !existWork(t, l, k, j, i))
//////				if (max_rest[j] + t[i] - (t[j] + l[j]) > max_rest[i]) {
//////					max_rest[i] = max_rest[j] + t[i] - (t[j] + l[j]);
//////					is_include_first[i] = is_include_first[j];
//////				}
//////		if (isLast(t, l, k, i))
//////			max_rest[i] += n - (t[i] + l[i] - 1);
//////		if (is_include_first[i])
//////			m = max(m, max_rest[i]);
//////	}
//////	cout << m << endl;
//////	return 0;
//////}